Antysymetria

Limit pamięci: 32 MB

Bajtazar studiuje różne napisy złożone z zer i jedynek. Niech będzie takim napisem, przez będziemy oznaczać odwrócony (czyli "czytany wspak") napis , a przez będziemy oznaczać napis powstały z przez zamianę wszystkich zer na jedynki, a jedynek na zera.

Bajtazara interesuje antysymetria, natomiast niezbyt lubi wszystko co symetryczne. Antysymetria nie jest tylko prostym zaprzeczeniem symetrii. Powiemy, że (niepusty) napis jest antysymetryczny, jeżeli dla każdej pozycji w , -ty znak od końca jest różny od -tego znaku, licząc od początku. W szczególności, niepusty napis złożony z zer i jedynek jest antysymetryczny wtedy i tylko wtedy, gdy . Na przykład, napisy 00001111 i 010101 są antysymetryczne, natomiast 1001 nie jest.

W zadanym napisie złożonym z zer i jedynek chcielibyśmy wyznaczyć liczbę jego spójnych (tj. jednokawałkowych) niepustych fragmentów, które są antysymetryczne. Jeżeli różne fragmenty odpowiadają takim samym słowom, to i tak należy je policzyć wielokrotnie.

Wejście

Pierwszy wiersz standardowego wejścia zawiera liczbę (), oznaczającą długość napisu. Drugi wiersz zawiera napis złożony z liter 0 i/lub 1 o długości . Napis ten nie zawiera żadnych odstępów.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą liczbę spójnych fragmentów wczytanego napisu, które są antysymetryczne.

Przykład

Dla danych wejściowych:

8
11001011

poprawną odpowiedzią jest:

7

Antysymetryczne fragmenty to: 01 (pojawia się dwukrotnie), 10 (także dwukrotnie), 0101, 1100 oraz 001011.

Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.